Finite State Machines (FSMs), also known as finite automata, depict behavioral models composed of inputs, states, transitions, and outputs (or actions). Two well known finite state machine types are Moore and Mealy FSMs. In Moore machines, the output depends on state, whereas in Mealy machines the output depends on transition. These FSM abstractions were described by their namesakes in the late 1950's and have been widely utilized in a variety of fields including mathematics, logic, linguistics and computer science, for the past half century. In practice, many FSMs employ both types of machines in combination. Other FSMs have also been described, as have methods to transform one type into another.
Specified FSMs can be classified into two groups: recognizers and transducers. Recognizers produce binary output: yes/true (recognized) or no/false (not recognized). Transducers generate output based on input and/or current state and are often used to control applications. Transducers transform (or map) ordered sets of input events into corresponding ordered sets of output events.
FSMs are used with some regularity to control computer systems and applications, both in hardware and software. In many applications, the specified FSMs are hard-wired or hard-coded, as the case may be, into the system or application. In general, the FSM is developed based upon a specific application, and methods or systems are required to provide for the creation or development of the FSM in accordance with the application requirements. Some customizable general purpose FSMs have been devised to aide in the development of control mechanisms for computer systems and applications.
An example of a system and method for implementing a FSM based upon configuration data is disclosed in U.S. Pat. No. 7,039,893. A FSM Engine is used to generate specific configurations for different state machines based on configuration data using a common method. This common configuration structure is used for all state machine implementations, and changes in the state machine design drive changes in the configuration data instead of in executable software. Multiple software state machines are thus implemented using a configurable approach. In addition, state machine processing is performed periodically and state transition events are handled without the need for an event driven operating system. The disclosed approach, however, has several deficiencies. For example, a new FSM is needed for each instance, and customized executable code, e.g., as described in the preferred embodiment the “configuration data” are C language code and header files, is produced from the FSM model. In addition, a new production-compilation-deployment cycle is needed to incorporate FSM model changes into running systems.
An alternative approach utilized web services-business process execution language (WS-BPEL) that provides both externalization and an execution engine. However, WS-BPEL does not enforce FSM control flows. Therefore, WS-BPEL flows can be written that do not conform to any FSM Specification. Another disadvantage of WS-BPEL is that there are no guarantees to model the entire flow, e.g. all states and state transitions, thus failing to provide any level of assurance or provability.
Expressing an FSM externally as Extensible Markup Language (XML) is also well known in the Artificial Intelligence (AI) and computer gaming literature (see for example http://www.igda.org/ai/report-2004/fsm.html or http://www.codeproject.com/csharp/xmlfsm.asp). These externally specified FSMs have not separated execution from state maintenance.
More generally, FSMs have been defined using state tables as in “The Virtual Finite State Machine Implementation Paradigm” (see http://www.lucent.com/minds/techjournal/pdf/winter_97/paper08.pdf). Again, these techniques have been used to generate customized code.
Finite State Machines (FSMs) have been employed to solve a wide variety of problems since their conception in the 1950's. They've often been embedded within applications. Some embedded FSMs have a distributed aspect. For example, in published U.S. Patent Application no. 2005/0169286 titled “Distributed finite state machine”, an embedded FSM is used to provide “a rate limiting mechanism in the router”. Although a particular distributed FSM is described, no instruction is directed toward a general system for defining and employing arbitrary, distributed FSMs. In U.S. Pat. No. 5,761,484 titled “Virtual interconnections for reconfigurable logic systems” another embedded distributed finite state machine is described, but no teaching on how to describe and implement arbitrary, distributed FSMs in a structured and systematic way is presented. In U.S. Pat. No. 5,909,369 titled “Coordinating the states of a distributed finite state machine” a method for coordinating the states of a distributed finite state machine is given. However, the previous methods fail to disclose a method and system to specify and manage user defined FSMs, including the behavior of FSMs, i.e., states, transitions and actions, and the distribution of FSM components in time and space.